大家好,我是羊小咩
今天要介紹的是 ECC , ECC 一樣是用基於數學難題,製作出來的安全機制
由於 ECC 本來就是一種艱澀的演算法,因此在內文 ECC 流程及原理精簡了很多步驟、演算法及一些數學領域的專業術語
像是幾何加法(geometric addition),代數加法(Algebraic addition)、純量乘法 (Scalar multiplication),阿爾貝群(Abelian group)...等,這些都不是三言兩語可以簡易理解的,都需要一定基礎觀念。
整體用我認為比較簡單扼要的方式進行闡述
之前讀書會分享過ECC 議題,大家也都是聽的一知半解,想把ECC簡潔說明真的很困難 Orz
希望整理出的這篇讓讀者對ECC 有初步的認識和 ECC 的美好(?)
橢圓曲線密碼學(英語:Elliptic Curve Cryptography,縮寫:ECC)是一種基於橢圓曲線數學的公開密鑰加密演算法。橢圓曲線在密碼學中的使用是在1985年由Neal Koblitz和Victor Miller分別獨立提出的。
ECC的主要優勢是它相比RSA加密演算法使用較小的密鑰長度並提供相當等級的安全性[1]。ECC的另一個優勢是可以定義群之間的雙線性映射,基於Weil對或是Tate對;雙線性映射已經在密碼學中發現了大量的應用,例如基於身份的加密。
PKI Algorithm | RSA | ECC |
---|---|---|
Key Size | Security: 280 @ 1024-bits | Security: 280 @160-bits |
Security: 2112 @ 2048-bits | Security: 2112 @224-bits | |
Security: 2128 @ 3072-bits | Security: 2128 @ 256-bits | |
Security: 2:92 @ 7680-bits | Security: 2192 @386-bits | |
Security: 2256 @ 15360-bits | Security: 2256 @512-bits | |
安全基礎 | 大數因數分解 | EC橢圖曲線上離散對數 |
優點 | 演算法容易說明,且同時可用做加解密 | 運算速度快,簽章長度較小 |
缺點 | 運算速度慢,簽章長度較大 | 理論較難理解,且實作技術較為複雜 |
從上表可以總結優點
安全性能更高
160位ECC 和 1024位RSA、DSA有相同的安全强度
處理速度更快
在計算速度上,ECC比RSA、DSA快得多
頻寬要求更低
儲存空間更小
ECC的密鑰大小參數,與RSA、DSA相比要小得多
非對稱加密算法中,之前最廣泛的 RSA 加密方法,逐漸開始被 ECC 取代
區塊鏈是基於 ECC 設計的,例如:使用ECC 製作出公鑰,經過Hash 得到地址,且此過程無法逆推還原
橢圓曲線是由以下形式的方程式定義 的平面曲線
其中a和b是實數。這類稱為 Weierstrass方程式
過曲線上的兩點P、Q畫一條直線,找到直線與橢圓曲線的交點 -R
交點關於x軸對稱位置的點,定義為P Q,即為加法。如下圖所示:PQ = R
上述方法無法解釋P P,即兩點重合的情況。因此在這種情況下,將橢圓曲線在 P 點的切線,與橢圓曲線的交點,交點關於x軸對稱位置的點,定義為P P,即2P,即為二倍運算
如果將A與-A相加,過A與-A的直線平行於y軸,可以認為直線與橢圓曲線相交於無窮遠點。
依照上面特性定義後可整理出
橢圓曲線方程式為y2=x3+ax+b
此曲線剛好對稱於**x軸(y=0)**這條直線
參數a及b必需滿足4a3+27b2≠0,才能確保沒有重根, 具有唯一解!
加法單位元素O為一無窮遠的點, 並滿足O=-O
此加法單位元素亦需滿足: 橢圓曲線上某三點共線其合為O
繪製的橢圓曲線。具有幾個有趣的屬性。
其中之一是水平對稱。曲線上的任何點都可以在x軸上反射並保持相同的曲線。一個更有趣的特性是,任何非垂直線最多將在三個地方與曲線相交。
將橢圓曲線比喻成擊球遊戲, 把球從A點擊向B點,
當再碰撞到曲線上的點後會反彈到(x軸以上或以下)另一邊的C點
先想像成把球在兩個點移動稱為"打點(dot)"
A dot B = C
A dot A = B
A dot C = D
... ... ...
這裡只有兩個點(稱為: 最初點&最終點)
將最初的點P自行打點 n次(as Private Key) 會得到一個最終點Q(as Public Key)
即使你知道"最初點"和"最終點"
要找出n是非常非常之困難!
橢圓曲線是連續的,容易被推算,因此,並不適合用於加密;
所以,我們必須把橢圓曲線變成離散的點
把橢圓曲線定義在有限域上,這時就會用到以質數為模的整數域
有限域GF(p)指給定某個質數p,由0、1、2……p-1共p個元素組成的整數集合中定義的加減乘除運算。
假設橢圓曲線為y² = x³ x 1,其在有限域GF(23)上時,寫作:
y² ≡ x³ x 1 (mod 23)
此時,橢圓曲線不再是一條光滑曲線,而是一些不連續的點,如下圖所示。以點(1,7)為例,7² ≡ 1³ 1 1 ≡ 3 (mod 23)。如此還有如下點:
(0,1) (0,22)
(1,7) (1,16)
(3,10) (3,13)
(4,0)
....
就可以使原本看起來是連續的曲線
轉換到有限域上
接著就可以進行貪食蛇遊戲(?)
從A點到B點為不垂直的線穿過曲EC線最多只會有三個交點!
當在碰撞到第三個交點時, 第三個交點一定可以在EC曲線x軸(以上或以下)找到一個對稱點C點
補充:在域空間曲線,大概是這樣的一個感覺
RSA 同演算法可以直接實現簽章及加密,ECC 需要分別實作
ECDSA (Elliptic Curve Digital Signature Algorithm)
ECIES (Elliptic Curve Integrated Encryption Scheme)
ECDH (Elliptic Curve Diffie–Hellman key Exchange)
設定出一個有限域Fp
略過選取曲線,和給定參數過程計算後
曲線已知E23(1,1)上兩點P(3,10),Q(9,7),求(1)-P,(2)P+Q,(3) 2P
圖片來源 https://www.zhihu.com/question/26662683
如果橢圓曲線上一點P,存在最小的正整數n使得數乘nP=O∞ ,則將n稱為P的階
若n不存在,則P是無限階的
圖片來源 https://www.zhihu.com/question/26662683
因此選定 n 後即可 計算出可得27P=-P
所以28P=O ∞ P的階為28
這些點做成了一個循環阿貝爾群
,其中生成元為P,階數為29
並從裡面選取基點,並開始計算
考慮K=kG ,其中K、G為橢圓曲線Ep(a,b)上的點,n為G的階(nG=O∞),k為小於n的整數。
則給定k和G,根據加法法則,計算K很容易
但反過來,給定K和G,求k就非常困難
其中k、K分別為私鑰、公鑰。
這就是橢圓曲線計算流程
設私鑰、公鑰分別為k、K,即K = kG,其中G為G點。
公鑰加密:
選擇隨機數r,將訊息M生成密文C,該密文是一個點對,即:
C = {rG, M rK},其中K為公鑰
私鑰解密:
M rK – k(rG) = M r(kG) – k(rG) = M
其中k、K分別為私鑰、公鑰。
橢圓曲線上的已知G和xG求x,是非常困難的,此即為橢圓曲線上的的離散對數問題。此處x即為私鑰,xG即為公鑰。
設私鑰、公鑰分別為k、K,即K = kG,其中G為G點。
私鑰簽名:
1、選擇隨機數r,計算點rG(x, y)。
2、根據隨機數r、訊息M的雜湊h、私鑰k,計算s = (h kx)/r。
3、將訊息M、和簽名{rG, s}發給接收方
公鑰驗證簽名:
1、接收方收到訊息M、以及簽名{rG=(x,y), s}。
2、根據訊息求雜湊h。
3、使用傳送方公鑰K計算:hG/s xK/s,並與rG比較,如相等即驗籤成功
原理如下:
hG/s xK/s = hG/s x(kG)/s = (h xk)G/s
= r(h xk)G / (h kx) = rG
ECC 一樣採用數學難題,進行設計,但難度比REA 質因數分寫還要難,而且運算比RSA 還要快
定義了一條橢圓曲線
因此 n = 19 , h = 1
圖片來源 :https://www.youtube.com/watch?v=F3zzNa42-tQ
詳細計算可以觀看影片
現實上,計算實會選用大的數字和質數,使其幾乎無法反推計算
ECC 一樣是用基於數學難題,製作出來的安全機制
我在 ECC 流程及原理精簡了很多步驟、演算法及一些數學領域的專業術語
像是幾何加法(geometric addition),代數加法(Algebraic addition)、純量乘法 (Scalar multiplication),阿爾貝群(Abelian group)...等,這些都不是三言兩語可以簡易理解的,都需要一定基礎觀念。
整體用我認為比較簡單扼要的方式進行闡述
之前讀書會分享過ECC 議題,大家也都是聽的一知半解,想把ECC簡潔說明真的很困難 Orz
希望整理出的這篇讓讀者對ECC 有初步的認識和 ECC 的美好(?)
https://en.wikipedia.org/wiki/Elliptic_curve
https://zh.wikipedia.org/wiki/RSA%E5%8A%A0%E5%AF%86%E6%BC%94%E7%AE%97%E6%B3%95
Elliptic Curve Cryptography: a gentle introduction
Elliptic Curve Cryptography: finite fields and discrete logarithms
Elliptic Curve Cryptography: ECDH and ECDSA
Elliptic Curve Cryptography: breaking security and a comparison with RSA
https://combohuang.pixnet.net/blog/post/212457468-ecc-(elliptic-curve-cryptosystem)
https://codertw.com/%E7%A8%8B%E5%BC%8F%E8%AA%9E%E8%A8%80/43964/
假設橢圓曲線為y² = x³ x 1,其在有限域GF(23)上時,寫作:
y² ≡ x³ x 1 (mod 23)
應該是y² ≡ x³ + x + 1 (mod 23)吧